package com.leetcode.字符串;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * <p>
 * 回文串 是正着读和反着读都一样的字符串。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 * <p>
 * 输入：s = "a"
 * 输出：[["a"]]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xaxi62/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 分割回文串 {

	//结果集
	List<List<String>> res = new ArrayList<>();
	//当前路径
	List<String> path = new ArrayList<>();
	//回文串判断表 isPalindrome[i][j]=s[i...j]
	boolean[][] isPalindrome;

	public List<List<String>> partition(String s) {
		int len = s.length();
		char[] arr = s.toCharArray();
		isPalindrome = new boolean[len][len];
		for (int i = 0; i < len; i++) {
			isPalindrome[i][i] = true;
		}
		//回文状态转移dp[i][j]=arr[i]==arr[j]&&dp[i+1][j-1]
		for (int j = 1; j < len; j++) {
			for (int i = 0; i < j; i++) {
				if (j - i < 3) {
					isPalindrome[i][j] = arr[i] == arr[j];
				} else {
					isPalindrome[i][j] = arr[i] == arr[j] && isPalindrome[i + 1][j - 1];
				}
			}
		}
		//深度优先搜索
		DFS(s, 0, s.length() - 1, isPalindrome);
		return res;
	}

	//N叉树深度优先搜索
	private void DFS(String s, int start, int end, boolean[][] isPalindrome) {
		if (start > end) {
			List<String> l = new ArrayList<>();
			l.addAll(path);
			res.add(l);
			return;
		}
		//N叉树分支遍历
		for (int len = 1; len <= end - start + 1; len++) {
			if (!isPalindrome[start][start + len - 1]) {
				continue;
			}
			//路径添加本分段
			path.add(s.substring(start, start + len));
			//下层继续深度优先搜索
			DFS(s, start + len, end, isPalindrome);
			//路径删除本分段
			path.remove(path.size() - 1);
		}
	}

	@Test
	public void test () {
		System.out.println(partition("aabcdcba"));
	}
}
